package org.example.leetCode;

/**
 * 28. 找出字符串中第一个匹配项的下标
 * 给你两个字符串 haystack 和 needle ，
 * 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
 * 如果 needle 不是 haystack 的一部分，则返回  -1 。
 */
public class Code28 {
    public int strStr(String haystack, String needle) {
        int m = needle.length();
        if (m == 0) return 0;
        char[] p = needle.toCharArray();
        char[] s = haystack.toCharArray();
        int[] next = new int[m + 1];
        next[0] = 0;
        //构建next数组
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && p[i] != p[j]) {
                j = next[j - 1];
            }
            //p[i]==p[j]相等，则取j++对应的数
            //不等，则j一定是0，取next[0]，即0
            if (p[i] == p[j]) j++;
            next[i] = j;
        }
        //kmp匹配过程
        for (int i = 0, j = 0; i < s.length; i++) {
            while (j > 0 && s[i] != p[j]) {
                j = next[j - 1];
            }
            if (s[i] == p[j]) j++;
            if (j == m) return i - m + 1;
        }
        return -1;


    }

    public static void main(String[] args) {
        Code28 solution = new Code28();

        // 测试用例 1
        String haystack1 = "sadbutsad";
        String needle1 = "sad";
        System.out.println("Test 1: " + solution.strStr(haystack1, needle1)); // 输出 0

        // 测试用例 2
        String haystack2 = "leetcode";
        String needle2 = "leeto";
        System.out.println("Test 2: " + solution.strStr(haystack2, needle2)); // 输出 -1

        // 测试用例 3
        String haystack3 = "abcabcd";
        String needle3 = "abcd";
        System.out.println("Test 3: " + solution.strStr(haystack3, needle3)); // 输出 3

        // 测试用例 4
        String haystack4 = "a";
        String needle4 = "a";
        System.out.println("Test 4: " + solution.strStr(haystack4, needle4)); // 输出 0

        // 测试用例 5
        String haystack5 = "aaa";
        String needle5 = "";
        System.out.println("Test 5: " + solution.strStr(haystack5, needle5)); // 输出 0
    }
}
